package com.zjsru.oneDay;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 一手顺子
 * <p>
 * 输入：hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
 * 输出：true
 * 解释：Alice 手中的牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。
 * <p>
 * 输入：hand = [1,2,3,4,5], groupSize = 4
 * 输出：false
 * 解释：Alice 手中的牌无法被重新排列成几个大小为 4 的组。
 */
public class isNStraightHand {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        /**
         * 模拟+哈希表+堆
         *
         * 使用优先队列维护（小根堆）所有的 hand[i]
         * 每次从优先队列（堆）中取出堆顶元素 t 来 尝试作为「顺子」的发起点/首个元素
         * （当然 t 能够作为发起点的前提是 t 仍是剩余元素，即实时维护的出现次数不为 00 ），
         * 然后用 tt 作为发起点/首个元素构造顺子，即对 [t, t + 1, ... , t + m - 1][t,t+1,...,t+m−1] 元素的出现次数进行 -1 操作。
         *
         * */
        Map<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> a - b);//保证每次取出的元素都是队列中权值最小的
        for (int i : hand) {
            map.put(i, map.getOrDefault(i, 0) + 1);
            pq.add(i);
        }
        while (!pq.isEmpty()) {
            int t = pq.poll();//poll()方法检索并删除此队列的头，如果此队列为空则返回null
            if (map.get(t) == 0) continue;
            for (int i = 0; i < groupSize; i++) {
                int cnt = map.getOrDefault((i + t), 0);
                if (cnt == 0) return false;
                map.put(t + i, cnt - 1);
            }
        }
        return true;
    }

    public static void main(String[] args) {
        isNStraightHand isNStraightHand = new isNStraightHand();
        int[] hand = new int[]{1, 2, 3, 6, 2, 3, 4, 7, 8};
        int groupSize = 3;
        System.out.println(isNStraightHand.isNStraightHand(hand, groupSize));
    }
}
